package com.leetcode.search;

import java.util.*;

/**
 * leetcode 127 单词接龙
 */
public class Solution127 {
    private static class Pair<k, v> {
        private k key;

        private v value;

        public Pair(k key, v value) {
            this.key = key;
            this.value = value;
        }

        public k getKey() {
            return key;
        }

        public void setKey(k key) {
            this.key = key;
        }

        public v getValue() {
            return value;
        }

        public void setValue(v value) {
            this.value = value;
        }
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }

        // 构建转换字典
        Map<String, ArrayList<String>> wordMap = new HashMap<>();
        for (String word : wordList) {
            for (int i = 0; i < word.length(); i++) {
                String key = word.substring(0, i) + "_" + word.substring(i+1);
                if (!wordMap.containsKey(key)) {
                    wordMap.put(key, new ArrayList<>(Collections.singleton(word)));
                } else {
                    ArrayList<String> words = wordMap.get(key);
                    words.add(word);
                    wordMap.put(key, words);
                }
            }
        }

        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(beginWord, 1));
        ArrayList<String> visited = new ArrayList<>(Collections.singleton(beginWord));
        while (!queue.isEmpty()) {
            Pair<String, Integer> pair = queue.remove();
            for (int i = 0; i < pair.getKey().length(); i++) {
                String key = pair.getKey().substring(0, i) + "_" + pair.getKey().substring(i+1);
                for (String word : getOrDefault(key, wordMap)) {
                    if (endWord.equals(word)) {
                        return pair.getValue() + 1;
                    }

                    if (!visited.contains(word)) {
                        visited.add(word);
                        queue.add(new Pair<>(word, pair.getValue() + 1));
                    }
                }
            }
        }
        return 0;
    }

    private List<String> getOrDefault(String key, Map<String, ArrayList<String>> wordMap) {
        if (wordMap.containsKey(key)) {
            return wordMap.get(key);
        } else {
            return Arrays.asList();
        }
    }

    public static void main(String[] args) {
        Solution127 solution127 = new Solution127();
        System.out.println(solution127.ladderLength("hit", "cog", Arrays.asList("hot", "dot", "lot", "dog", "log", "cog")));
    }
}
